1. Field
The following description relates to a packet scheduling, and more particularly, to a packet scheduling method and apparatus which allows multiple flows that require data transmission to the same output port of a network device such as a router to fairly share bandwidth.
2. Description of the Related Art
With the advent of diverse application services and increase of users, various methods including call admission control, buffer management, packet scheduling, congestion control, quality of service (QoS) routing, and the like have been researched to provide QoS in a network.
Packet scheduling is applied in various forms to a network device to guarantee network performance. A weighted fair queuing (WFQ) algorithm and a fair queuing (FQ) algorithm similar to WFQ which introduce virtual time and calculate a virtual start time and a virtual termination time of each packet allocate the calculated virtual start time or the calculated virtual termination time to a packet as a timestamp, and perform packet scheduling according to an arrangement based on the timestamp value. Thus, the WFQ and FQ algorithms have a complexity of O(logN) when there are present N flows.
On the other hand, in other packet scheduling methods such as stop-end-go or hierarchical-round-Robin, which divide a time axis frame-by-frame and perform packet scheduling based on a frame at which a packet arrives, system performance is substantially affected by a frame size, and inter-frame synchronization is required, which makes it difficult to apply the method to a large-scale network.